#!/usr/bin/env python
# -*-coding:utf-8 -*-

"""
算法描述
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。
"""


# 方法一
def bubbleSort(array):
    if len(array) < 2:
        return array
    else:
        isSorted = False
        counter = 0
        while not isSorted:
            isSorted = True
            for idx in range(len(array) - 1 - counter):
                if array[idx] > array[idx + 1]:
                    isSorted = False
                    (array[idx + 1], array[idx]) = (array[idx], array[idx + 1])
            counter += 1
        return array


def bubbleSort2(array):
    if len(array) < 2:
        return array
    else:
        for i in range(len(array)):
            for j in range(len(array) - i - 1):
                if array[j] > array[j + 1]:
                    (array[j + 1], array[j]) = (array[j], array[j + 1])

    return array


arr = [1, 3, 4, 2, 9, 7, 8]
sorted_arr = bubbleSort(arr)
print(sorted_arr)

arr2 = [1, 3, 4, 2, 9, 7, 8]
sorted_arr2 = bubbleSort2(arr2)
print(sorted_arr2)
